1. Field of the Invention
The invention relates to time division multiplexers/demultiplexers (TDM), particularly with respect to time slot assignment procedures for frame building.
2. Description of the Prior Art
Present day communication networks comprise a plurality of nodes interconnected by a plurality of communication links or transmission facilities. For example, the T1 transmission facility provides communication at a rate of 1.544 Mbps (megabits per second). Alternatively, lower rate as well as higher rate links may be utilized such as the 56 Kbps (kilobits per second) DDS link or the T3 facility having a capacity equivalent to 28 T1 links. I/O devices such as data terminals, PBXs, CPUs and the like are connected to the various nodes to communicate information to each other. The communicated information is, for example, data or voice and is transmitted over the links in digital form. Communication between two particular I/O devices connected at diverse nodes is effected by establishing a circuit or channel therebetween. The information is communicated over the channel through the various nodes and over the various interconnecting links between the two I/O devices. Thus, the network provides channels between the various I/O equipments desiring to use the network for intercommunication therebetween.
Typically, an I/O device transmits data at a uniform clock rate. In order for an I/O device to receive the information, it must lock to the incoming data stream. The incoming bits usually vary from nominal uniform spacing and the amount of non-uniformity is denoted as jitter. A particular channel can tolerate a predetermined amount of jitter before data transmission is disrupted.
The information is transmitted from one node to the next over the interconnecting facility in frames at a constant transmission rate. Each frame is comprised of a plurality of contiguous time slots, for example, 3860 time slots of 400 bps each. The data rate associated with each time slot is denoted as the "bandwidth" of the slot. The term bandwidth is also utilized to denote the data rate of the link as well as the data rate of the device.
In order to establish a channel between two I/O devices, a plurality of time slots of the frame are assigned to the channel. The number of slots per frame required is determined by the bandwidth of the device and the bandwidth of the time slots. The frame width, in terms of the total number of slots, is dependent on the bandwidth of a slot and the bandwidth of the links. In the above example, if the device requires a 9600 bps synchronous rate, 24 time slots in the frame are assigned to the channel (9600/400) . The remaining time slots in the frame are assigned to other channels. This technique is denoted as time division multiplexing (TDM). Thus, each node of the network is implemented with a TDM multiplexer. The TDM multiplexer includes a microprocessor that assigns the channels requiring service to the time slots of the frame and stores the channel assignments in frame tables in memory. Each time slot may convey a data bit, a data character or one or more data bytes.
It is a desideratum in the time division multiplexing technology to assign the time slots to each channel as uniformly as possible across the frame. Uniform time slot dispersion is desired so that the receiving I/O device can phase lock to the data stream. For example, with a frame that is 1000 slots wide, a channel requiring 100 slots per frame is ideally positioned on the network if successive slots of the channel have 10 slots therebetween. If the channel required 50 time slots on the frame, the ideal spacing would be 20 slots between successive assignments. In the prior art, a heuristic trial and error procedure is generally utilized to assign the channels desiring service to a frame. Such a procedure is often referred to as frame building. The number of slots in the frame required for the first channel is calculated. If the frame is initially empty, the first channel placed on the network may be assigned time slots with substantially ideal uniformity. As additional channels are placed on line, slots required for ideal positioning may be occupied by a previously assigned channel thereby resulting in time slot collisions. When collision occurs, a non-uniform placement of a channel slot is attempted. If the non-uniformity exceeds the maximum jitter that the channel can tolerate, a different assignment of the time slots to the channel is attempted. For example, a new starting slot for the channel may be tried to determine if acceptable jitter for the channel can be achieved. On a crowded network, it may be necessary to attempt a complete frame reassignment in order to endeavor to accommodate a new channel. Thus, it is appreciated that the time slots for a channel cannot be assigned arbitrarily. The positions of the time slots assigned to a channel are in accordance with the maximum jitter that the channel can tolerate. Because of the heuristic nature of the prior art procedures, placement of a channel on the network is not guaranteed even though adequate spare bandwidth exists.
It is appreciated that the prior art heuristic frame building procedures utilize very time consuming search procedures in endeavoring to place channels on the network. Consequently, in the event of network failure, the prior art frame building procedures introduce inordinate delays in rerouting and reconnecting disconnected channels. Additionally, significant amounts of bandwidth are wasted utilizing the prior art approaches. Even though spare bandwidth exists which is adequate for the placement of a new channel, the prior art procedures may not successfully interleave the new channel into the spare bandwidth without exceeding the jitter tolerance for the channel. At that point, the network would be considered fully occupied even though unused bandwidth is available.
Output buffering may be utilized, to some extent, to obviate the problems caused by time slot non-uniformity on a channel. A reserve of characters must be accumaulated in a buffer before uniform transmission from the buffer can be initiated to the I/O device. Excessive buffering can introduce undesirably large network propagation delays.
The prior art frame building procedures create serious problems in the implementation of features such as channel bumping and bandwidth reservation. A priority channel that desires access to a crowded network may replace one or more lower priority channels. However, even though the bandwidth economized from the lower priority channels is adequate, it may not be possible to accommodate the high priority channel at the required jitter level. Additionally, reservation of adequate bandwidth for a channel does not guarantee that it will be possible to accommodate that channel in the frame.
Some networks utilize large bandwidth time slots in order to obviate the above-described problems. The larger the time slot bandwidth, the smaller will be the number of slots in the frame. Since bandwidth can only be assigned in large increments because of the data rates of present day I/O devices, this approach is excessively wasteful of bandwidth.
As discussed above, the prior art frame building procedures endeavor to assign to a channel time slots that are dispersed in the frame as uniformly as possible to minimize inter-character jitter thereby reducing network delays. When endeavoring to place a channel on the network, various starting slots for the channel are attempted to ascertain the most uniform distribution for that channel considering the time slot occupancy of previously assigned channels. If the inter-character jitter is greater than can be tolerated by the channel, the channel is denied access to the network even though adequate spare bandwidth exists. Although the frame is considered to be occupied to the acceptable level of inter-character jitter, a significant amount of bandwidth is wasted. Alternatively, the frame may be rebuilt to accommodate the channel utilizing the excessively time consuming prior art procedures. Non-uniform placement of the time slots causes jitter in the phase lock acquisition of the receiving I/O devices. As discussed above, the channel can tolerate a certain amount of such inter-character jitter but excessive non-uniformity imposed by the prior art heuristic approaches may deny channels access to the network.